package demo11;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Day2 {
    private int sumSlow(int n) {
        int i = n;
        int sum = 0;
        while(i != 0) {
            int a = i % 10;
            sum += (a * a);
            i /= 10;
        }
        return sum;
    }
    private int sumFast(int m) {
        int i = m;
        int sum = 0;
        for(int j = 0 ; j < 2; j++) {
            sum = 0;
            while (i != 0) {
                int a = i % 10;
                sum += (a * a);
                i /= 10;
            }
            i = sum;
        }
        return sum;
    }
    public boolean isHappy(int n) {
        int slow = n;
        int fast = n;
        while(slow == n || slow != fast) {
            slow = sumSlow(slow);
            fast = sumFast(fast);
            if(slow == fast) {
                return false;
            }
            if(fast == 1) {
                break;
            }
        }
        return true;
    }

    //优化写法
    private int sum(int n) {
        int i = n;
        int sum = 0;
        while(i != 0) {
            int a = i % 10;
            sum += (a * a);
            i /= 10;
        }
        return sum;
    }

    public boolean isHappy1(int n) {
        int slow = n;
        int fast = sum(n);
        while(slow != fast) {
            slow = sum(slow);
            fast = sum(sum(fast));
            if(fast == 1) {
                break;
            }
            if(slow == fast) {
                return false;
            }

        }
        return true;
    }

    public int maxArea(int[] height) {
        int head = 0;
        int last = height.length - 1;
        int max = (last - head) * (Math.min(height[head], height[last]));;
        while(head != last) {
            if(height[head] > height[last]) {
                last--;
            }else {
                head++;
            }
            int a = (last - head) * (Math.min(height[head], height[last]));
            if(a > max) {
                max = a;
            }
        }
        return max;
    }

    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        int cur = nums.length - 1;
        while(cur >= 2) {
            int left = 0;
            int right = cur - 1;
            while(left < right) {
                if((nums[left] + nums[right]) > nums[cur]) {
                    count += (right - left);
                    right--;
                }else {
                    left++;
                }
            }
            cur--;
        }
        return count;
    }

    public int[] twoSum(int[] price, int target) {
        int[] ret = new int[2];
        int left = 0;
        int right = price.length - 1;
        while(left < right) {
            int sum = price[left] + price[right];
            if(sum < target) {
                left++;
            }else if(sum > target){
                right--;
            }else {
                ret[0] = price[left];
                ret[1] = price[right];
                break;
            }
        }
        return ret;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new LinkedList<>();
        Arrays.sort(nums);

        int cur = 0;
        while(cur < nums.length - 2) {
            int left = cur + 1;
            int right = nums.length - 1;
            while(left < right) {
                int sum = nums[left] + nums[right] + nums[cur];
                while(left < right && nums[left] == nums[left + 1]) {
                    left++;
                }
                while(left < right && nums[right] == nums[right - 1]) {
                    right--;
                }
                if(sum < 0) {
                    left++;
                }else if(sum > 0){
                    right--;
                }else {
                    List<Integer> list = new LinkedList<>();
                    list.add(nums[cur]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    lists.add(list);
                    left++;
                    right--;
                    //去重
                }

            }

            //去重
            while(cur + 1 < nums.length && nums[cur] == nums[cur + 1]) {
                cur++;
            }
            cur++;

        }
        return lists;
    }


    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> lists = new LinkedList<>();
        int a = 0;
        int n = nums.length;
        while (a < n) {
            int b = a + 1;
            while (b < n) {
                int left = b + 1;
                int right = n - 1;
                long num1 = (long)target;
                long des = num1 - nums[a] - nums[b];
                while (left < right) {
                    long sum = nums[left] + nums[right];
                    if (sum < des) {
                        left++;
                    }else if (sum > des) {
                        right--;
                    }else {
                        List<Integer> list = new LinkedList<>();
                        list.add(nums[a]);
                        list.add(nums[b]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        lists.add(list);
                        left++;
                        right--;
                        // 去重
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    }
                }
                //去重
                b++;
                while(b < n && nums[b] == nums[b - 1]) {
                    b++;
                }
            }
            //去重
            a++;
            while (a < n && nums[a] == nums[a - 1]) {
                a++;
            }
        }
        return lists;
    }
}
